package Algorithm.dynamicProgramming.introduct;

/**
 * 343. 整数拆分 https://leetcode.cn/problems/integer-break
 * 题目简述：给定一个正整数n，将其拆分为k个正整数的和（k >= 2），并使这些整数的乘积最大化。返回你可以获得的最大乘积。
 */
public class IntegerBreak {

    /**
     * 动态规划
     * 1. 定义dp: dp[i]即为整数i拆分最大乘积
     * 2. 确定递推公式：整数i拆分乘式的第一个数j有从1至i-1共i-1种可能，而后面所有数乘积的最大值即为max((i-j), dp[i-j])
     *              ，故dp[i] = max(j*(i-j), j*dp[i-j])
     * 3. 初始化dp: dp[2] = 1
     * 4. 开始递推，对于每个数i，遍历[1, i-1]，寻找最大值dp[i] = max(j*(i-j), j*dp[i-j])
     */
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        //开始递推
        for (int i = 3;i <= n;i++) {
            //对于每个数i，遍历[1, i-1]，寻找最大值dp[i] = max(j*(i-j), j*dp[i-j])
            for (int j = 1;j < i;j++) {
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }

    /**
     * 进一步分析，当dp[i]取到最大值时，j一定是拆分后乘积不大于j，故j必然是小于5
     * 故可进一步优化
     */
    public int integerBreak2(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        for (int i = 3;i <= n;i++) {
            int t = Math.min(i, 5);
            //对于每个数i，遍历[1, t]，寻找最大值dp[i]
            for (int j = 1;j < t;j++) {
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
}
